package cn.xkai.exercise.b;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @description: 从中序与后序遍历序列构造二叉树
 * @author: kaixiang
 * @date: 2022/7/16
 **/
public class Solution69 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        if (len == 0) return null;
        return dfs(inorder, postorder, 0, len - 1, 0, len - 1);
    }

    TreeNode dfs(int[] inorder, int[] postorder, int head1, int tail1, int head2, int tail2) {
        if (head2 > tail2) return null;

        int val = postorder[tail2];
        TreeNode root = new TreeNode(val);
        if (head2 == tail2) return root;

        int mid = 0;  //拆分点mid的位置是相对的，因为h1!=h2
        while (inorder[head1 + mid] != val) mid++;

        root.left = dfs(inorder, postorder, head1, head1 + mid - 1, head2, head2 + mid - 1);
        root.right = dfs(inorder, postorder, head1 + mid + 1, tail1, head2 + mid, tail2 - 1);

        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
